#pragma once

#include "container_common.h"

namespace mdtx::online::container
{
    constexpr std::size_t skiplist_max_level = 32;

    template <class TV, class TP>
    class skiplist_iterator
    {
    private:
        TP node;
        skiplist_iterator(TP node)
            : node{node}
        {
        }

    public:
        using value_type = TV;
        using pointer = value_type *;
        using reference = value_type &;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::forward_iterator_tag;

        skiplist_iterator()
            : node{nullptr}
        {
        }

        // Implements basic LegacyInputIterator
        friend bool operator==(const skiplist_iterator &lhs, const skiplist_iterator &rhs)
        {
            return lhs.node == rhs.node;
        }
        friend bool operator!=(const skiplist_iterator &lhs, const skiplist_iterator &rhs)
        {
            return lhs.node != rhs.node;
        }
        reference operator*()
        {
            return node->v;
        }
        pointer operator->()
        {
            return std::addressof(node->v);
        }
        skiplist_iterator &operator++()
        {
            node = node->next[0];
            return *this;
        }
        skiplist_iterator operator++(int)
        {
            skiplist_iterator it(node);
            node = node->next[0];
            return it;
        }

        template <class T, class C>
        friend class skiplist;

        template <class T, class C>
        friend class iskiplist;
    };

    template <class T, class C = std::less<T>>
    class skiplist
    {
    public:
        using value_type = T;
        using value_compare = C;
        using size_type = std::size_t;
        using reference = value_type &;
        using const_reference = const value_type &;

    private:
        // Node
        struct node_type;
        using node_ptr_type = node_type *;
        struct node_type
        {
            value_type v;
            std::vector<node_ptr_type> next;
            template <class __value_type>
            node_type(__value_type &&v, size_type d)
                : v(std::forward<__value_type>(v)),
                  next(d, nullptr)
            {
            }
        };
        template <class __value_type>
        node_ptr_type mk_node(__value_type &&v, size_type d)
        {
            return new node_type(std::forward<__value_type>(v), d);
        }
        void rm_node(node_ptr_type node)
        {
            delete node;
        }

        // Skiplist algorithms
        using fp_type = std::array<node_ptr_type, skiplist_max_level>;
        // Find lower bound
        node_ptr_type find_cp(node_ptr_type from, const value_type &v) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && _cp(node->next[lv]->v, v))
                {
                    node = node->next[lv];
                }
            }
            return node;
        }
        node_ptr_type find_cp_fp(node_ptr_type from, const value_type &v, fp_type &fp) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && _cp(node->next[lv]->v, v))
                {
                    node = node->next[lv];
                }
                fp[lv] = node;
            }
            return node;
        }
        // Find upper bound
        node_ptr_type find_cpeq(node_ptr_type from, const value_type &v) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && !_cp(v, node->next[lv]->v))
                {
                    node = node->next[lv];
                }
            }
            return node;
        }
        node_ptr_type find_cpeq_fp(node_ptr_type from, const value_type &v, fp_type &fp) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && !_cp(v, node->next[lv]->v))
                {
                    node = node->next[lv];
                }
                fp[lv] = node;
            }
            return node;
        }

        // Resource
        size_type _size, _mxlv;
        node_ptr_type _head;

        // Comparator
        value_compare _cp;

        // Random engine
        std::default_random_engine _rgen;
        std::uniform_int_distribution<> _runi;
        size_type random_depth()
        {
            size_type depth = 1;
            while (_runi(_rgen))
            {
                ++depth;
            }
            return std::min(depth, _mxlv);
        }

    public:
        // Resource management

        skiplist(size_type max_level, const value_compare &compare = value_compare())
            : _size(0),
              _mxlv(max_level),
              _head(mk_node(value_type(), _mxlv)),
              _cp(compare),
              _rgen((std::random_device())()),
              _runi(0, 1)
        {
        }

        ~skiplist()
        {
            node_ptr_type node;
            while (_head)
            {
                node = _head;
                _head = _head->next[0];
                rm_node(node);
                _size -= 1;
            }
        }

        skiplist(const skiplist &other)
            : skiplist(1, other._cp)
        {
            merge(other);
        }

        skiplist(skiplist &&other)
            : _size(other._size),
              _mxlv(other._mxlv),
              _head(other._head),
              _cp(std::move(other._cp)),
              _rgen((std::random_device())()),
              _runi(0, 1)
        {
            other._head = nullptr;
        }

        // We do not deal with allocators, and stick to simple copy-and-swap idiom
        skiplist &operator=(skiplist other)
        {
            swap(*this, other);
            return *this;
        }

        friend void swap(skiplist &lhs, skiplist &rhs)
        {
            using std::swap;
            swap(lhs._size, rhs._size);
            swap(lhs._mxlv, rhs._mxlv);
            swap(lhs._head, rhs._head);
            swap(lhs._cp, rhs._cp);
        }

    public:
        // Iterator
        using iterator = skiplist_iterator<value_type, node_ptr_type>;
        using const_iterator = skiplist_iterator<const value_type, node_ptr_type>;
        iterator begin()
        {
            return iterator(_head->next[0]);
        }
        const_iterator cbegin() const
        {
            return const_iterator(_head->next[0]);
        }
        iterator end()
        {
            return iterator(nullptr);
        }
        const_iterator cend() const
        {
            return const_iterator(nullptr);
        }

        // Lookup

        size_type count(const value_type &v) const
        {
            size_type total = 0;
            node_ptr_type node = find_cp(_head, v);
            while (node->next[0] && !_cp(v, node->next[0]->v))
            {
                ++total;
                node = node->next[0];
            }
            return total;
        }

        bool contains(const value_type &v) const
        {
            node_ptr_type node = find_cp(_head, v);
            return node->next[0] && !_cp(v, node->next[0]->v);
        }

        const_iterator find(const value_type &v) const
        {
            const_iterator it{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it.node = node->next[0];
            }
            return it;
        }

        iterator find(const value_type &v)
        {
            iterator it{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it.node = node->next[0];
            }
            return it;
        }

        const_iterator lower_bound(const value_type &v) const
        {
            node_ptr_type node = find_cp(_head, v);
            return const_iterator(node->next[0]);
        }

        iterator lower_bound(const value_type &v)
        {
            node_ptr_type node = find_cp(_head, v);
            return iterator(node->next[0]);
        }

        const_iterator upper_bound(const value_type &v) const
        {
            node_ptr_type node = find_cpeq(_head, v);
            return const_iterator(node->next[0]);
        }

        iterator upper_bound(const value_type &v)
        {
            node_ptr_type node = find_cpeq(_head, v);
            return iterator(node->next[0]);
        }

        std::pair<const_iterator, const_iterator> equal_range(const value_type &v) const
        {
            const_iterator it1{}, it2{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it1.node = node->next[0];
                it2.node = find_cpeq(node, v);
            }
            return {std::move(it1), std::move(it2)};
        }

        std::pair<iterator, iterator> equal_range(const value_type &v)
        {
            iterator it1{}, it2{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it1.node = node->next[0];
                it2.node = find_cpeq(node, v);
            }
            return {std::move(it1), std::move(it2)};
        }

        size_type size() const
        {
            return _size;
        }

        bool empty() const
        {
            return _size == 0;
        }

        // Modifier

        void clear()
        {
            node_ptr_type node = _head->next[0];
            std::fill(_head->next.begin(), _head->next.end(), nullptr);
            while (node)
            {
                node_ptr_type tmp = node;
                node = node->next[0];
                rm_node(tmp);
                _size -= 1;
            }
        }

        iterator insert(const value_type &v)
        {
            fp_type fp{};
            find_cp_fp(_head, v, fp);
            // create node
            size_type depth = random_depth();
            node_ptr_type newnode = mk_node(v, depth);
            // create link
            for (size_type lv = 0; lv < depth; ++lv)
            {
                newnode->next[lv] = fp[lv]->next[lv];
                fp[lv]->next[lv] = newnode;
            }
            _size += 1;
            return iterator(newnode);
        }

        iterator insert(value_type &&v)
        {
            fp_type fp{};
            find_cp_fp(_head, v, fp);
            // create node
            size_type depth = random_depth();
            node_ptr_type newnode = mk_node(std::move(v), depth);
            // create link
            for (size_type lv = 0; lv < depth; ++lv)
            {
                newnode->next[lv] = fp[lv]->next[lv];
                fp[lv]->next[lv] = newnode;
            }
            _size += 1;
            return iterator(newnode);
        }

        value_type erase(const value_type &v)
        {
            fp_type fp{};
            node_ptr_type node = find_cp_fp(_head, v, fp);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                node = node->next[0];
                for (size_type lv = 0; lv < node->next.size(); ++lv)
                {
                    fp[lv]->next[lv] = node->next[lv];
                }
                value_type removed{std::move(node->v)};
                rm_node(node);
                _size -= 1;
                return removed;
            }
            else
            {
                return {};
            }
        }

        void merge(const skiplist &other)
        {
            // Create new skiplist, and swap with *this
            skiplist newlist(std::max(_mxlv, other._mxlv), _cp);

            fp_type fp{};
            std::fill(fp.begin(), fp.end(), newlist._head);

            node_ptr_type nodeL = _head->next[0];
            node_ptr_type nodeR = other._head->next[0];
            while (nodeL || nodeR)
            {
                if (!nodeL)
                {
                    std::swap(nodeL, nodeR);
                }
                if (nodeR && _cp(nodeR->v, nodeL->v))
                {
                    std::swap(nodeL, nodeR);
                }
                size_type depth = newlist.random_depth();
                node_ptr_type node = newlist.mk_node(nodeL->v, depth);
                for (size_type lv = 0; lv < depth; ++lv)
                {
                    fp[lv]->next[lv] = node;
                    fp[lv] = node;
                }
                newlist._size += 1;
                nodeL = nodeL->next[0];
            }

            std::swap(*this, newlist);
        }

        template <class C2>
        void merge(const skiplist<T, C2> &other)
        {
            // Slow algorithm due to different comparator
            node_ptr_type node = other._head->next[0];
            while (node)
            {
                insert(node->v);
                node = node->next[0];
            }
        }

        value_type pop()
        {
            node_ptr_type node = _head->next[0];
            if (node)
            {
                for (size_type lv = 0; lv < node->next.size(); ++lv)
                {
                    _head->next[lv] = node->next[lv];
                }
                value_type result{std::move(node->v)};
                rm_node(node);
                _size -= 1;
                return result;
            }
            else
            {
                return {};
            }
        }

        const_reference top() const
        {
            return _head->next[0]->v;
        }

        // WARNING: this breaks encapsulation and can mess up object lifetime. Use with caution.
        reference top()
        {
            return _head->next[0]->v;
        }
    };

    template <class T, class C = std::less<T>>
    class iskiplist
    {
    public:
        using value_type = T;
        using value_compare = C;
        using size_type = std::size_t;
        using reference = value_type &;
        using const_reference = const value_type &;

    private:
        // Node
        struct node_type;
        using node_ptr_type = node_type *;
        struct node_type
        {
            value_type v;
            std::vector<node_ptr_type> next;
            std::vector<size_type> span;
            template <class __value_type>
            node_type(__value_type &&v, size_type d)
                : v(std::forward<__value_type>(v)),
                  next(d, nullptr),
                  span(d, 0)
            {
            }
        };
        template <class __value_type>
        node_ptr_type mk_node(__value_type &&v, size_type d)
        {
            return new node_type(std::forward<__value_type>(v), d);
        }
        void rm_node(node_ptr_type node)
        {
            delete node;
        }

        // Skiplist algorithms
        using fp_type = std::array<node_ptr_type, skiplist_max_level>;
        using fs_type = std::array<size_type, skiplist_max_level>;
        // Find lower bound
        node_ptr_type find_cp(node_ptr_type from, const value_type &v) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && _cp(node->next[lv]->v, v))
                {
                    node = node->next[lv];
                }
            }
            return node;
        }
        node_ptr_type find_cp_fp(node_ptr_type from, const value_type &v, fp_type &fp, fs_type &fs) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && _cp(node->next[lv]->v, v))
                {
                    fs[lv] += node->span[lv];
                    node = node->next[lv];
                }
                fp[lv] = node;
            }
            return node;
        }
        // Find upper bound
        node_ptr_type find_cpeq(node_ptr_type from, const value_type &v) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && !_cp(v, node->next[lv]->v))
                {
                    node = node->next[lv];
                }
            }
            return node;
        }
        node_ptr_type find_cpeq_fp(node_ptr_type from, const value_type &v, fp_type &fp, fs_type &fs) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && !_cp(v, node->next[lv]->v))
                {
                    fs[lv] += node->span[lv];
                    node = node->next[lv];
                }
                fp[lv] = node;
            }
            return node;
        }
        // Seek index
        node_ptr_type seek_span(node_ptr_type from, size_type span) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && span >= node->span[lv])
                {
                    span -= node->span[lv];
                    node = node->next[lv];
                }
            }
            return node;
        }
        node_ptr_type seek_span_fp(node_ptr_type from, size_type span, fp_type &fp) const
        {
            node_ptr_type node = from;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && span >= node->span[lv])
                {
                    span -= node->span[lv];
                    node = node->next[lv];
                }
                fp[lv] = node;
            }
            return node;
        }

        // Resource
        size_type _size, _mxlv;
        node_ptr_type _head;

        // Comparator
        value_compare _cp;

        // Random engine
        std::default_random_engine _rgen;
        std::uniform_int_distribution<> _runi;
        size_type random_depth()
        {
            size_type depth = 1;
            while (_runi(_rgen))
            {
                ++depth;
            }
            return std::min(depth, _mxlv);
        }

    public:
        // Resource management

        iskiplist(size_type max_level, const value_compare &compare = value_compare())
            : _size(0),
              _mxlv(max_level),
              _head(mk_node(value_type(), _mxlv)),
              _cp(compare),
              _rgen((std::random_device())()),
              _runi(0, 1)
        {
        }

        ~iskiplist()
        {
            node_ptr_type node;
            while (_head)
            {
                node = _head;
                _head = _head->next[0];
                rm_node(node);
                _size -= 1;
            }
        }

        iskiplist(const iskiplist &other)
            : iskiplist(1, other._cp)
        {
            merge(other);
        }

        iskiplist(iskiplist &&other)
            : _size(other._size),
              _mxlv(other._mxlv),
              _head(other._head),
              _cp(std::move(other._cp)),
              _rgen((std::random_device())()),
              _runi(0, 1)
        {
            other._head = nullptr;
        }

        // We do not deal with allocators, and stick to simple copy-and-swap idiom
        iskiplist &operator=(iskiplist other)
        {
            swap(*this, other);
            return *this;
        }

        friend void swap(iskiplist &lhs, iskiplist &rhs)
        {
            using std::swap;
            swap(lhs._size, rhs._size);
            swap(lhs._mxlv, rhs._mxlv);
            swap(lhs._head, rhs._head);
            swap(lhs._cp, rhs._cp);
        }

    public:
        // Iterator
        using iterator = skiplist_iterator<value_type, node_ptr_type>;
        using const_iterator = skiplist_iterator<const value_type, node_ptr_type>;
        iterator begin()
        {
            return iterator(_head->next[0]);
        }
        const_iterator cbegin()
        {
            return const_iterator(_head->next[0]);
        }
        iterator end()
        {
            return iterator(nullptr);
        }
        const_iterator cend()
        {
            return const_iterator(nullptr);
        }

        // Lookup

        size_type count(const value_type &v) const
        {
            size_type total = 0;
            node_ptr_type node = find_cp(_head, v);
            while (node->next[0] && !_cp(v, node->next[0]->v))
            {
                ++total;
                node = node->next[0];
            }
            return total;
        }

        bool contains(const value_type &v) const
        {
            node_ptr_type node = find_cp(_head, v);
            return node->next[0] && !_cp(v, node->next[0]->v);
        }

        const_iterator find(const value_type &v) const
        {
            const_iterator it{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it.node = node->next[0];
            }
            return it;
        }

        iterator find(const value_type &v)
        {
            iterator it{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it.node = node->next[0];
            }
            return it;
        }

        const_iterator lower_bound(const value_type &v) const
        {
            node_ptr_type node = find_cp(_head, v);
            return const_iterator(node->next[0]);
        }

        iterator lower_bound(const value_type &v)
        {
            node_ptr_type node = find_cp(_head, v);
            return iterator(node->next[0]);
        }

        const_iterator upper_bound(const value_type &v) const
        {
            node_ptr_type node = find_cpeq(_head, v);
            return const_iterator(node->next[0]);
        }

        iterator upper_bound(const value_type &v)
        {
            node_ptr_type node = find_cpeq(_head, v);
            return iterator(node->next[0]);
        }

        std::pair<const_iterator, const_iterator> equal_range(const value_type &v) const
        {
            const_iterator it1{}, it2{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it1.node = node->next[0];
                it2.node = find_cpeq(node, v);
            }
            return {std::move(it1), std::move(it2)};
        }

        std::pair<iterator, iterator> equal_range(const value_type &v)
        {
            iterator it1{}, it2{};
            node_ptr_type node = find_cp(_head, v);
            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                it1.node = node->next[0];
                it2.node = find_cpeq(node, v);
            }
            return {std::move(it1), std::move(it2)};
        }

        size_type size() const
        {
            return _size;
        }

        bool empty() const
        {
            return _size == 0;
        }

        // TODO: generalise
        size_type rank_lb(const value_type &v) const
        {
            size_type rank = 0;
            node_ptr_type node = _head;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && _cp(node->next[lv]->v, v))
                {
                    rank += node->span[lv];
                    node = node->next[lv];
                }
            }
            return rank;
        }

        size_type rank_ub(const value_type &v) const
        {
            size_type rank = 0;
            node_ptr_type node = _head;
            for (size_type lv = node->next.size(); lv--;)
            {
                while (node->next[lv] && !_cp(v, node->next[lv]->v))
                {
                    rank += node->span[lv];
                    node = node->next[lv];
                }
            }
            return rank;
        }

        // Do not allow direct assignment/alteration, use rank_ref() instead
        const_reference operator[](size_type i) const
        {
            // we need to skip head node, thus i + 1
            node_ptr_type node = seek_span(_head, i);
            return node->next[0]->v;
        }

        // Modifier

        void clear()
        {
            node_ptr_type node = _head->next[0];
            std::fill(_head->next.begin(), _head->next.end(), nullptr);
            std::fill(_head->span.begin(), _head->span.end(), 0);
            while (node)
            {
                node_ptr_type tmp = node;
                node = node->next[0];
                rm_node(tmp);
                _size -= 1;
            }
        }

        size_type insert(const value_type &v)
        {
            fp_type fp{};
            fs_type fs{};
            find_cp_fp(_head, v, fp, fs);
            // create node
            size_type depth = random_depth();
            node_ptr_type newnode = mk_node(v, depth);
            // create link
            size_type traversed = 0;
            for (size_type lv = 0; lv < depth; ++lv)
            {
                newnode->next[lv] = fp[lv]->next[lv];
                fp[lv]->next[lv] = newnode;
                newnode->span[lv] = fp[lv]->span[lv] - traversed;
                fp[lv]->span[lv] = traversed + 1;
                traversed += fs[lv];
            }
            for (size_type lv = depth; lv < _mxlv; ++lv)
            {
                fp[lv]->span[lv] += 1;
                traversed += fs[lv];
            }
            _size += 1;
            return traversed;
        }

        size_type insert(value_type &&v)
        {
            fp_type fp{};
            fs_type fs{};
            find_cp_fp(_head, v, fp, fs);
            // create node
            size_type depth = random_depth();
            node_ptr_type newnode = mk_node(std::move(v), depth);
            // create link
            size_type traversed = 0;
            for (size_type lv = 0; lv < depth; ++lv)
            {
                newnode->next[lv] = fp[lv]->next[lv];
                fp[lv]->next[lv] = newnode;
                newnode->span[lv] = fp[lv]->span[lv] - traversed;
                fp[lv]->span[lv] = traversed + 1;
                traversed += fs[lv];
            }
            for (size_type lv = depth; lv < _mxlv; ++lv)
            {
                fp[lv]->span[lv] += 1;
                traversed += fs[lv];
            }
            _size += 1;
            return traversed;
        }

        value_type erase(const value_type &v)
        {
            fp_type fp{};
            fs_type fs{};
            node_ptr_type node = find_cp_fp(_head, v, fp, fs);

            if (node->next[0] && !_cp(v, node->next[0]->v))
            {
                node = node->next[0];
                size_type depth = node->next.size();
                for (size_type lv = 0; lv < depth; ++lv)
                {
                    fp[lv]->span[lv] += node->span[lv] - 1;
                    fp[lv]->next[lv] = node->next[lv];
                }
                for (size_type lv = depth; lv < _mxlv; ++lv)
                {
                    fp[lv]->span[lv] -= 1;
                }
                value_type removed{std::move(node->v)};
                rm_node(node);
                _size -= 1;
                return removed;
            }
            else
            {
                return {};
            }
        }

        value_type erase_rank(size_type rank)
        {
            fp_type fp{};
            node_ptr_type node = seek_span_fp(_head, rank, fp);

            if (node->next[0])
            {
                node = node->next[0];
                size_type depth = node->next.size();
                for (size_type lv = 0; lv < depth; ++lv)
                {
                    fp[lv]->span[lv] += node->span[lv] - 1;
                    fp[lv]->next[lv] = node->next[lv];
                }
                for (size_type lv = depth; lv < _mxlv; ++lv)
                {
                    fp[lv]->span[lv] -= 1;
                }
                value_type removed{std::move(node->v)};
                rm_node(node);
                _size -= 1;
                return removed;
            }
            else
            {
                return {};
            }
        }

        void merge(const iskiplist &other)
        {
            // Create new iskiplist, and swap with *this
            iskiplist newlist(std::max(_mxlv, other._mxlv), _cp);

            fp_type fp{};
            std::fill(fp.begin(), fp.end(), newlist._head);

            node_ptr_type nodeL = _head->next[0];
            node_ptr_type nodeR = other._head->next[0];
            while (nodeL || nodeR)
            {
                if (!nodeL)
                {
                    std::swap(nodeL, nodeR);
                }
                if (nodeR && _cp(nodeR->v, nodeL->v))
                {
                    std::swap(nodeL, nodeR);
                }
                size_type depth = newlist.random_depth();
                node_ptr_type node = newlist.mk_node(nodeL->v, depth);
                for (size_type lv = 0; lv < newlist._mxlv; ++lv)
                {
                    fp[lv]->span[lv] += 1;
                }
                for (size_type lv = 0; lv < depth; ++lv)
                {
                    fp[lv]->next[lv] = node;
                    fp[lv] = node;
                }
                newlist._size += 1;
                nodeL = nodeL->next[0];
            }

            std::swap(*this, newlist);
        }

        template <class C2>
        void merge(const skiplist<T, C2> &other)
        {
            // Slow algorithm due to different comparator
            node_ptr_type node = other._head->next[0];
            while (node)
            {
                insert(node->v);
                node = node->next[0];
            }
        }

        // WARNING: this breaks encapsulation and can mess up object lifetime. Use with caution.
        reference top_ref()
        {
            return _head->next[0]->v;
        }

        reference rank_ref(size_type rank)
        {
            node_ptr_type node = seek_span(_head, rank);
            return node->next[0]->v;
        }
    };

}
